package Alibaba;

/**
 * @author zhangmin
 * @create 2022-01-18 15:28
 */
public class maxSubArray53 {

    /**
     * 53、最大子数组和
     * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * dp：dp[i]表示以地i个元素为结尾的最大子数组和
     * */
    public int maxSubArray(int[] nums) {
        int n=nums.length;
        int dp_pre=nums[0],res=dp_pre;
        for (int i = 1; i < n; i++) {
            int dp=Math.max(dp_pre+nums[i],nums[i]);
            res=Math.max(res,dp);
            dp_pre=dp;
        }
        return res;
    }
}
